package LC;

import java.util.*;

/**
 * https://leetcode.com/problems/merge-intervals/description/
 * Given a collection of intervals, merge all overlapping intervals.
 * For example,
 * Given [1,3],[2,6],[8,10],[15,18],
 * return [1,6],[8,10],[15,18].
 */
public class LC_056_MergeIntervals_Sort_List {
    public static void main(String[] args) {
        ArrayList<Interval> list = new ArrayList<>();
        list.add(new Interval(1, 3));
        list.add(new Interval(2, 6));
        list.add(new Interval(15, 18));
        list.add(new Interval(8, 10));
        List<Interval> res = Solution.merge(list);
        System.out.println(res.toString());
    }

    static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }

        @Override
        public String toString() {
            return "[" + start + " " + end + "]";
        }
    }

    static class Solution {
        static List<Interval> merge(List<Interval> intervals) {
            if (intervals.size() <= 0)
                return intervals;

            //根据interval的start排序
            Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start < o2.start ? -1 : 1;
                }
            });

            //intervals.sort(Comparator.comparingInt(o -> o.start));

            System.out.println(intervals.toString());

            for (int i = 0; i + 1 < intervals.size(); i++) {
                Interval current = intervals.get(i);
                Interval next = intervals.get(i + 1);
                if (current.end >= next.start) {
                    current.end = Math.max(current.end, next.end);
                    intervals.remove(i + 1);
                    i--;
                }
            }
            return intervals;
        }
    }
}
